import java.util.Arrays;
import java.util.List;

public class Solution648 {

    static class Trie{
        boolean end;
        Trie[] tries=new Trie[26];

        void insert(String s){
            Trie node=this;
            for (char c : s.toCharArray()) {
                if (node.tries[c-'a']==null){
                    node.tries[c-'a']=new Trie();
                }
                node=node.tries[c-'a'];
            }
            node.end=true;
        }

        String find(String s){
            Trie node=this;
            int count=0;
            for (char c:s.toCharArray()){
                if (node.tries[c-'a']==null){
                    return s;
                }
                count++;
                node=node.tries[c-'a'];
                if (node.end){
                    return s.substring(0,count);
                }
            }
            return s;
        }
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        Trie trie=new Trie();
        for (String s : dictionary) {
            trie.insert(s);
        }
        String[] strings=sentence.split(" ");
        for (int i=0;i<strings.length;i++){
            strings[i]=trie.find(strings[i]);
        }
        StringBuilder s=new StringBuilder();
        s.append(strings[0]);
        for (int i=1;i<strings.length;i++){
            s.append(' ').append(strings[i]);
        }
        return s.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution648().replaceWords(Arrays.asList("cat","bat","rat"),"the cattle was rattled by the battery"));
    }
}
